Graph Coloring: Chromatic Number ($\chi(G)$)

Implement the Greedy Algorithm to find an upper bound for the Chromatic Number.

ā“ The Coloring Challenge

The **Chromatic Number ($\chi(G)$)** is the smallest number of colors needed to color the vertices of a graph $G$ such that no two adjacent vertices share the same color. Finding the exact chromatic number is generally **NP-hard**.

We will use the **Greedy Coloring Algorithm**, which provides a fast and practical **upper bound** on $\chi(G)$.

Input Section (Adjacency Matrix)

Graph Visualization (Initial):

šŸ’” The Greedy Coloring Strategy

The Core Rule: Minimum Excluded (MEX) Color

The greedy approach colors vertices one by one based on a fixed order (in this demo, the input order $0, 1, 2, \dots$ ).

  1. **Vertex Order:** Process vertices in a fixed sequence (e.g., $V_0, V_1, V_2, \dots$).
  2. **Check Neighbors:** For the current vertex $u$, check the colors already assigned to its neighbors.
  3. **Assign MEX:** Assign the **smallest positive integer color (1, 2, 3, ...)** that is *not* used by any of $u$'s neighbors.
  4. **Repeat:** Continue until all vertices are colored. The number of colors used is the result.

Color Palette Used:

1
2
3
4
5

šŸŽ¬ Step-by-Step Coloring Demo

Graph Not Loaded. Click "Prepare Graph Data" first.

Process Log:

Log will appear here as you step through the process.

Coloring Progress:

Final Chromatic Number (Greedy Result):

?

šŸ“Š Analysis & Limitations

Time Complexity

O(VĀ² + V * $\Delta$)

Where $V$ is vertices and $\Delta$ is max degree. In the worst case for dense graphs, this is **O(VĀ³)** or $O(V \cdot (V+V)) = O(V^2)$ if neighbor check is $O(V)$ and finding the color is $O(V)$. Very efficient!

Space Complexity

O(VĀ² + V)

Required to store the Adjacency Matrix ($O(V^2)$) and the color array ($O(V)$).

Limitation of Greedy Coloring

The greedy algorithm is a **heuristic**, meaning it doesn't always find the true minimum chromatic number ($\chi(G)$). The result depends heavily on the **order** in which the vertices are processed. Changing the vertex order (e.g., using saturation degree) can often yield a better, or minimum, result, but the simple order used here is the most basic implementation.